#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/10/10
# @Author   :Changshu
# @File     :practice_235.py

# 235. 二叉搜索树的最近公共祖先
# 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

'''两次遍历，需要存储两条路径
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
	if root is None:
		return None
	pathofP=getPath(root,p)
	pathofQ=getPath(root,q)
	n=len(pathofP) if len(pathofP)<=len(pathofQ) else len(pathofQ)
	i=0
	while i<n:
		if i+1 is not n:
			if pathofP[i+1] is not pathofQ[i+1]:
				return pathofP[i]
		i+=1
	return pathofP[-1] if i==len(pathofP) else pathofQ[-1]

def getPath(root: TreeNode, target: TreeNode) -> list:
	p = root
	path = [p]
	while p != target:
		if p.val > target.val:
			p = p.left
		else:
			p = p.right
		path.append(p)
	return path
'''

'''一次遍历'''
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
	if root is None:
		return None
	node=root
	while node is not p or node is not q:
		if node.val>p.val and node.val>q.val:
			node=node.left
		elif node.val < p.val and node.val < q.val:
			node=node.right
		else:
			break

	return node

def preOrder(root:TreeNode):
	if root:
		print(root.val,end=' ')
		preOrder(root.left)
		preOrder(root.right)


if __name__ == '__main__':
	'''二叉搜索树范例1
	node1 = TreeNode(6)
	node2_1 = TreeNode(2)
	node2_2 = TreeNode(8)
	node3_1 = TreeNode(0)
	node3_2 = TreeNode(4)
	node3_3 = TreeNode(7)
	node3_4 = TreeNode(9)
	node4_1 = TreeNode(3)
	node4_2 = TreeNode(5)

	node1.left = node2_1
	node1.right = node2_2
	node2_1.left = node3_1
	node2_1.right = node3_2
	node2_2.left = node3_3
	node2_2.right = node3_4
	node3_2.left = node4_1
	node3_2.right = node4_2
	'''

	'''范例2'''
	node1=TreeNode(2)
	node2=TreeNode(1)
	node1.left=node2

	preOrder(node1)
	print()
	# r=getPath(node1,node4_1)
	# for p in r:
	# 	print(p.val,end='->')

	# r=lowestCommonAncestor(node1,node4_1,node3_3)
	r = lowestCommonAncestor(node1, node2, node1)
	print(r.val)